package cn.edu.anan.datastructure.line;

/**
 * 顺序队列：基于数组实现
 * @param <E>
 */
public class ArrayQueue<E> {
    private Object[] items;
    private  int n;

    // 队列需要两个下标：对头下标索引、队尾下标索引
    private int head;
    private int tail;

    public ArrayQueue(int capacity){
        this.items = new Object[capacity];
        this.n = capacity;
    }

    /**
     * 入队操作：
     */
    public boolean enqueue(E e){
        // 检查队列是否满
        // 队列满条件 tail==n && head == 0
        if(tail == n){

            // 检查对头是否没有出队
            if(head == 0){
                return false;
            }

            // 如果已经有元素出队，则向对头移动数据
            for (int i = head; i < tail ; i++) {
                items[i - head] = items[i];
            }

            tail = tail - head;
            head = 0;
        }

        // 入队
        items[tail] = e;
        tail ++;

        return true;
    }

    /**
     * 出队操作：
     */
    public E dequeue(){
        // 检查队列是否空
        // 队列空条件：head == tail
        if(head == tail){
            return null;
        }

        // 出队
        E e = (E)items[head];
        head ++;

        return e;
    }

}
